package org.example;

/**
 * 二分查找相关知识
 * 作者：祝鑫
 * 时间：2025，5，25
 */
public class BinarySearch {
    /**
     *
     * @param a 数组
     * @param target 目标值
     * @return
     */
    public static int BinarySearchBasic(int[] a, Integer target) {
        int i = 0, j = a.length - 1; //设置指针初值
        while (i <= j) { //如果i<j，意味着数组内还有内容
            int m = (j + i) >>> 1;//无符号右移运算
            if (target < a[m]) {
                j = m - 1;
            } else if (target > a[m]) {
                i = m + 1;
            } else if (a[m] == target) {
                return m;
            }
        }
        return -1;
    }

    /**
     * 二查找平衡版
     *
     * @param a 数组
     * @param target 目标值
     * @return
     */
    //二分查找平衡版本 解决左右查询不平衡问题
    public static int BinarySearchBalance(int[] a, Integer target) {
        int i = 0, j = a.length;
        while (1 < j - i) {
            int m = (j + i) >>> 1;
            if (target < a[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (a[i] == target) {
            return i;
        } else {
            return -1;
        }
    }


    /**
     * 二分查找查询重复元素，返回最左侧元素leftmost
     * @param a 数组
     * @param target 目标追
     * @return
     */
    public static int BinarySearchLeftmost1(int[] a, Integer target) {
        int i = 0, j = a.length - 1; //设置指针初值
        int candidate = -1;
        while (i <= j) { //如果i<j，意味着数组内还有内容
            int m = (j + i) >>> 1;//无符号右移运算
            if (target < a[m]) {
                j = m - 1;
            } else if (target > a[m]) {
                i = m + 1;
            } else if (a[m] == target) {
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }


    /**
     * 二分查找查询重复元素，返回>=target的最左侧元素
     * @param a 数组
     * @param target 目标值
     * @return 返回>=target的最左侧元素
     */
    public static int BinarySearchLeftmost2(int[] a, Integer target) {
        int i = 0, j = a.length - 1; //设置指针初值
        while (i <= j) { //如果i<j，意味着数组内还有内容
            int m = (j + i) >>> 1;//无符号右移运算
            if (target <= a[m]) {
                j = m - 1;
            } else if (target > a[m]) {
                i = m + 1;
            }
        }
        return i;
    }


    /**
     * 二分查找查询重复元素，返回最右侧元素rightmost
     * @param a 数组
     * @param target 目标值
     * @return 返回最右侧元素
     */
    public static int BinarySearchRightmost1(int[] a, Integer target) {
        int i = 0, j = a.length - 1; //设置指针初值
        int candidate = -1;
        while (i <= j) { //如果i<j，意味着数组内还有内容
            int m = (j + i) >>> 1;//无符号右移运算
            if (target < a[m]) {
                j = m - 1;
            } else if (target > a[m]) {
                i = m + 1;
            } else if (a[m] == target) {
                candidate = m;
                j = m + 1 ;
            }
        }
        return candidate;
    }


    /**
     * 二分查找查询重复元素，返回<=target目标值最右侧元素
     * @param a 数组
     * @param target 目标值
     * @return 返回<=target目标值最右侧元素
     */
    public static int BinarySearchRightmost2(int[] a, Integer target) {
        int i = 0, j = a.length - 1; //设置指针初值

        while (i <= j) { //如果i<j，意味着数组内还有内容
            int m = (j + i) >>> 1;//无符号右移运算
            if (target < a[m]) {
                j = m - 1;
            } else if (target >= a[m]) {
                i = m + 1;
            }
        }
        return i-1;
    }
}
